
\subsection{Motivation - Das Gummibärchenproblem}
Ich habe $X$ Gummibärchen. 
\begin{itemize}
\item Verteile ich diese Gummibärchen gleichmäßig an \textbf{4} Leute, bleiben \textbf{2} Gummibärchen übrig
\item Verteile ich diese Gummibärchen gleichmäßig an \textbf{7} Leute, bleiben \textbf{3} Gummibärchen übrig
\end{itemize}
Wie viele Gummibärchen habe ich?\medskip

Etwas verallgemeinert:
\[
 x \equiv 2 \mod 4
\]
\[
 x \equiv 3 \mod 7
\]
Mit hinreichend langer Bedenkzeit können eine oder mehrere der folgenden Lösungen gefunden werden:
$$ x = 10 \text{ oder }x = 38\text{ oder }x = 66\text{ oder }... $$
Dabei stellen sich folgende Fragen: 
\begin{itemize}
\item Sind das alle Lösungen? 
\item Wie viele Lösungen gibt es? 
\item Wie kann ich die Lösung für schwierigere \textit{simultane Kongruenzen} lösen?
\end{itemize}
\subsubsection*{Allgemeine Lösung bei zwei Moduln}
Seien $m_1$ und $m_2$ teilerfremd (also $\gcd(m_1, m_2)=1$). Zu lösen sei das Kongruenzsystem:
\[
 x\equiv a_1\mod m_1
\]
\[
 x\equiv a_2\mod m_2
\]
Man bestimmt die Zahlen $y_1$ und $y_2$ folgendermaßen:
\[
 m_2~*~y_1 \equiv 1 \mod m_1
\]
\[
 m_1~*~y_2 \equiv 1 \mod m_2
\]
Dann ist eine Lösung $\mathbf{x=a_1*y_1*m_2+a_2*y_2*m_1}$, denn
\[
 x\equiv a_1*y_1*m_2+a_2*y_2*m_1 \equiv a_1*y_1*m_2 \equiv a_1*1\equiv a_1 \mod m_1
\]
\[
 x\equiv a_1*x_1*m_2+a_2*y_2*m_1 \equiv a_2*y_2*m_1 \equiv a_2*1 \equiv a_2 \mod m_2
\]
Weitere Lösungen ergeben sich durch $x+z*m_1*m_2$ mit $z \in \mathbb{N} $
\subsubsection*{Lösung des Beispiels}
\[
 7*y_1\equiv 1 \mod 4
\]
\[
 4*y_2 \equiv 1 \mod 7
\]
Lösung von $7*y_1\equiv 1 \mod 4$ mittels Erweiterter Euklidischer Algorithmus:\\
\begin{table}[htpd]
\centering
\begin{tabular}{|c|c|c|c|c|}
\hline 
a & b & q & x & y \\ 
\hline 
7 & 4 & 1 & -1 & 2 \\ 
\hline 
4 & 3 & 1 & 1 & -1 \\ 
\hline 
3 & 1 & 3 & 0 & 1 \\ 
\hline 
\end{tabular} 
\end{table}
\\daraus folgt: $-1 \mod 4 \Leftrightarrow 3 \mod 4 \Rightarrow y_1 = 3$.\\
Bei 2 Moduln erhält man nach Berechnung von $y_1$ automatisch $y_2$ durch die Darstellung:\\
\[
1=\gcd(m_1, m_2)=m_2*y_1 + m_1*y_2
\]
\[
\Rightarrow 1=7*3 + 4*y_2 \Rightarrow y_2=-5 \Rightarrow y_2=2
\]

$\Rightarrow $ $x=2*7*3+3*4*2=42*24=66$ (oder $94,~122,~150,~\ldots$)\\\medskip

Lösung für Repräsentanten in $\Z_{m_1 m_2} = \{ 0, 1, \ldots, m_1 m_2 - 1 \}$ erfolgt durch Reduktion um mod $m_1m_2$:\\
Hier also $66 \mod 28 = 10$.

\subsection{Lösung für $n$ Moduln \buchmann{3.15}}
Seien $m_1,...,m_m$ natürliche Zahlen, die \textbf{paarweise teilerfremd} (d.h. $\gcd(m_i, m_j) = 1$ für $i \ne j$) sind, und seien $a_1,...,a_m$ ganze Zahlen:
\begin{equation} \label{eq:solve}
x \equiv a_1 \mod m_1,\quad x \equiv a_2 \mod m_2, \quad ...~, x \equiv a_n \mod m_n
\end{equation}
Dann hat die simultane Kongruenz (\ref{eq:solve}) eine Lösung $x$, die eindeutig ist $\mod m = \prod_{i=1}^{n}m_i$.
\subsubsection{Berechnung}
Um eine simultane Kongruenz zu lösen wird folgendermaßen vorgegangen (gegeben seien simultane Kongruenzen wie in (\ref{eq:solve})).

Setze:
\begin{equation} \label{eq:m}
m=\prod_{i=1}^{n}m_i, \quad M_i=m/m_i, \quad 1 \leq i \leq n
\end{equation}
Es gilt:
\[
gcd(m_i,~M_i)=1,\quad 1 \leq i \leq n
\]
weil die $m_i$ paarweise teilerfremd sind.\\
 
Wir berechnen $y_i \in \mathbb{Z}, 1 \leq i \leq n$ mit
\begin{equation} \label{eq:yi}
y_iM_i \equiv 1 \mod m_i,~1 \leq i \leq n
\end{equation}

Dann setzen wir
\begin{equation} \label{eq:x}
x=(\sum_{i=1}^{n}a_iy_iM_i) \mod m
\end{equation}

\subsubsection{Beispiel \buchmann{3.15.1}}
Zu lösen ist die simultane Kongruenz:
\[
x \equiv 2 \mod 4,\quad x \equiv 1 \mod 3,\quad x \equiv 0 \mod5
\]
Wir berechnen $m$ und $M_i$ mittels Formel \ref{eq:m}.
\[
m=\prod_{i=1}^{n}m_i=4*3*5=60
\]
\[
M_1=\frac{m}{m_1}=\frac{60}{4}=15
\]
\[
M_2=\frac{m}{m_2}=\frac{60}{3}=20
\]
\[
M_3=\frac{m}{m_3}=\frac{60}{5}=12
\]
Dann werden alle $y_1$ für $~1 \leq i \leq n$ mittels Formel \ref{eq:yi} errechnet.

\begin{itemize}
\item $y_1M_1 \equiv 1 \mod m_1 \Leftrightarrow y_1*15 \equiv 1 \mod 4 \Leftrightarrow y_1*3 \equiv 1 \mod 4 \Leftrightarrow -y_1 \equiv 1 \mod 4 \quad \Rightarrow \mathbf{y_1=-1}$
\item $y_2M_2 \equiv 1 \mod m_2 \Leftrightarrow y_2*20 \equiv 1 \mod 3 \Leftrightarrow y_2*2 \equiv 1 \mod 3 \Leftrightarrow -y_2 \equiv 1 \mod 3 \quad \Rightarrow \mathbf{y_2=-1}$
\item $y_3M_3 \equiv 1 \mod m_3 \Leftrightarrow y_2*12 \equiv 1 \mod 5 \Leftrightarrow y_3*2 \equiv 1 \mod 5 \Leftrightarrow 2*y_3 \equiv 1 \mod 5 \quad \Rightarrow \mathbf{y_3=3}$
\end{itemize}
Aus Formel \ref{eq:x} folgt:
\[
x=(\sum_{i=1}^{n}a_iy_iM_i) \mod m=2*-1*15+1*-1*20+0*3*12 \mod 60=-30-20 \mod 60=-50 \mod 60=\mathbf{10}
\]
\subsubsection*{Warum geht das?}
Es wird nun gezeigt, dass dies eine Lösung der simultanen Kongruenz (\ref{eq:solve}) ist.\\
Aus (\ref{eq:yi}) folgt:
\[
a_iy_iM_i \equiv a_1 \mod m_i,~1 \leq i \leq n
\]
Weil für $j \neq i$ die Zahl $m_i$ ein Teiler von $M_j$ ist, gilt:
\[
a_jy_jM_j \equiv 0 \mod m_i,~1 \leq i,j \leq n, i \neq j
\]
Daraus folgt:
\[
x \equiv a_iy_iM_i + \sum_{j=1, i \neq j}^{n}a_jy_jM_j \equiv a_iy_iM_i + 0 \equiv a_iy_iM_i \equiv a_i*1 \equiv a_i \mod m_i ,~1 \leq i \leq n
\]
\subsection{Anwendung}
Durch den chinesischen Restsatz können modulare Berechnung effizienter gemacht werden. Dies ist z.B. bei der RSA-Entschlüsselung auf Chipkarten der Fall. Anstatt modulo $n=pq$ zu rechnen wird modulo $p$ und modulo $q$ gerechnet und das Ergebnis kombiniert.\\
Die Berechnung von $m^d \mod n$ mit dem Chinesischen Restsatz erfordert ebenso viele Quadrierungen und Multiplikationen wie ohne den Chinesischen Restsatz. Jedoch nehmen wir an, dass der RSA-Modul $n$ eine $k$-Bit Zahl ist und dass die Primfaktoren $q$ und $p$ $k/2$-Bit-Zahlen sind.\\
Quadrieren und Multiplizieren von halb so langen Operanden erfordert nur ein Viertel (1/4) des Rechenaufwandes. Die Entschlüsselung unter Verwendung des chinesischen Restsatzes ist also viermal so schnell wie die Standard-Entschlüsselungsmethode (siehe \buchmann{9.3.9}).
\subsubsection*{Beispiel \buchmann{9.3.9}}
\label{sub:Bsp}
Alice möchte den Schlüsseltext $c$ entschlüsseln. Ihr privater Schlüssel sei $d$. Alice berechnet:
\[
m_p \equiv c^d \mod p, \quad m_q=c^d \mod q
\]
und löst dann die simultane Kongruenz
\[
m \equiv m_p \mod p, \quad m=m_q \mod q
\]
Um die Kongruenz zu lösen müssen mit dem Erweiterten Euklidischen Algorithmus die Zahlen $y_p$ und $y_q$ mit der Formel
\[
y_p p + y_q q = 1
\]
errechnet und in folgende Formel eingesetzt werden (siehe auch Abschnitt 'Allgemeine Lösung bei zwei Moduln'):
\[
m=(m_py_qq+m_qy_pp) \mod n
\]
\medskip
\textbf{Achtung:}\\
Natürlich muss Alice zuvor keine Primfaktorzerlegung von $n$ durchführen, da dies nicht mit polynomiellem Aufwand durchzuführen ist. Da die Zahlen $y_pp \mod n$ und $y_qq \mod n$ aber nicht von dem Schlüsseltext $c$ abhängig sind, können diese vorberechnet werden (z.B. bei der Schlüsselerzeugung).
\medskip

\textbf{Weitere Optimierung:}\\
Bei der Berechnung von $m_p \equiv c^d \mod p$ kann nochmals optimieren werden, indem $d_p = d \mod (p-1)$ als Exponent verwendet, da $c^d \equiv c^{d_p} \mod p$.
\textbf{Beweis:}\\
\[
d_p=d\mod p-1 \Rightarrow d=k(p-1)+d_p
\]
\[
c^d=c^{k(p-1)+d_p} \Leftrightarrow (c^{p-1})^k c^{dp} = 1*c^{dp}
\]
\subsection{Low Exponent Attack \buchmann{9.3.7}}
Wird ein kleiner öffentliche Schlüssel $e$ bei der RSA-Verschlüsselung gewählt, so kann die Verschlüsselung effizient realisiert werden. Dabei ist die Wahl von $e=2$ ausgeschlossen, weil $\varphi (n)=(p-1)(q-1)$ gerade ist und $gcd(e,(p-1)(q-1))=1$ gelten muss.\\
Der kleinste Verschlüsselungsexponent ist also $e=3$. Die Verwendung dieses Exponenten ist aber gefährlich, da ein Angreifer die \textit{Low Exponent Attack} anwenden kann, wie nun gezeigt wird.\\\medskip

\textbf{Theorem} Seien:
\begin{itemize}
\item $e \in \mathbb{N}$
\item $n_1,n_2,\ldots,n_e \in \mathbb{N}$ paarweise teilerfremd 
\item $m \in \mathbb{N}~mit~0\leq m <n_i$ für alle $i$ mit $1 \leq i \leq e$
\item Sei $c \in \mathbb{N}$ und $0 \leq c \leq \prod_{i=1}^{e}n_i$ mit $c \equiv m^e \mod n_i$  für alle $i$ mit $1 \leq i \leq e$
\end{itemize}
dann folgt: $c=m^e$ (Beweis \buchmann{9.3.11})\\\medskip

Das heißt die ganze Zahl $c$ erfüllt die simultane Kongruenz aus Formel (\ref{eq:solve}) und ist der kleinste nicht negative Wert mit dieser Eigenschaft. Da nicht modulo gerechnet wird kann effizient die e-te Wurzel gezogen werden.\\\medskip

Die Low Exponent Attack kann man immer dann anwenden, wenn ein Klartext $m$ mit dem gleichen $e$ und zueinander paarweisen teilerfremden Moduln verschlüsselt wird.\\

\begin{figure}[hbtp]
\caption{Beispiel Low Exponent Attack}
\centering
\includegraphics[scale=0.5]{gfx/Low_exp_att.png}
\end{figure}
Ein Angreifer Oskar kann den Klartext $m$ folgendermaßen berechnen. Er kennt die Schlüsseltexte $c_i=m^e \mod n_i,~ 1 \leq i \leq e$. Mit dem chinesischen Restsatz berechnet er eine ganze Zahl $c$ mit $c \equiv c_i \mod n_i,~1\leq i\leq e$ und $0\leq c < \prod_{i=1}^{e}n_i$. Nach dem oben genannten Theorem kann Oskar $m$ finden, indem er aus $c$ die e-te Wurzel zieht (dies ist in Polynomzeit möglich).
\subsubsection*{Beispiel \buchmann{9.3.12}}
Wir wählen $e=3,~n_1=143,~n_2=391,~n_3=899$ und den zu verschlüsselnden Klartext $m=135$.\\
Dann ist:
\begin{itemize}
\item $c_1=m^e \mod n_1=135^3 \mod 143=60$
\item $c_2=m^e \mod n_2=135^3 \mod 391=203$
\item $c_3=m^e \mod n_3=135^3 \mod 899=711$
\end{itemize}
Wie in Abschnitt \ref{sub:Bsp} werden nun $y_1,~y_2,~y_3$ mit Formel \ref{eq:yi} berechnet.
\begin{itemize}
\item Aus $y_1n_2n_3 \equiv 1 \mod n_1$ folgt $y_1=-19$ 
\item Aus $y_2n_1n_3 \equiv 1 \mod n_2$ folgt $y_2=-62$
\item Aus $y_3n_1n_2 \equiv 1 \mod n_3$ folgt $y_3=262$
\end{itemize}
Dann ist $c=(c_1y_1n_2n_3 + c_2y_2n_1n_3 + c_3y_3n_1n_2 ) \mod n_1n_2n_3 = 2460375$ und $m=2460375^\frac{1}{3}=135$